15 Advanced Algorithms Problems

Algorithmics 2025

Area of Study 2

Advanced algorithm design

Key knowledge:

  • tree search by backtracking and its applications
  • the application of heuristics and randomised search to overcoming the soft limits of computation, including the limitations of these methods
  • hill climbing on heuristic functions, the A* algorithm and the simulated annealing algorithm
  • the graph colouring, 0-1 knapsack and travelling salesman problems and heuristic methods for solving them

Area of Study 2

Key skills:

  • apply the divide and conquer, dynamic programming and backtracking design patterns to design algorithms and recognise their usage within given algorithms
  • develop different algorithms for solving the same problem, using different algorithm design patterns, and compare their suitability for a particular application
  • apply heuristics methods to design algorithms to solve computationally hard problems
  • explain the application of heuristics and randomised search approaches to intractable problems, including the graph colouring, 0-1 knapsack and travelling salesman problems

Some classic problems

Each of these problems has a decision version and an optimisation version

Optimisation problem

  • Goal: Find the best solution according to some objective.
  • Output: The actual solution and/or its optimal value.
  • Nature: Search for the best among many possible solutions.

Some classic problems

Each of these problems has a decision version and an optimisation version

Decision problem

  • Goal: Answer yes/no — does a solution exist that meets a certain condition?
  • Output: Boolean (yes or no).
  • Nature: Confirm if a feasible solution exists

Decision and Optimisation

  • Decision problems are often easier to solve

  • Optimisation to Decision -> set a threshold/target value.

  • Decision to Optimisation -> search (linear or binary) over possible thresholds to find the best one.

    • Reduces the search space and makes the problem more manageable

Graph colouring

  • Optimisation problem: What is the minimum number of colours needed to colour a graph such that no two adjacent vertices share the same colour?

  • Decision problem: can a graph \(G\) be coloured with at most \(k\) colours so that no two adjacent vertices share a colour?

  • Complexity:

    • Decision problem is NP-complete for \(k \ge 3\).
    • Optimisation version is NP-hard.
    • Special cases (e.g., \(k=2\)) solvable in polynomial time.

Graph colouring

  • Applications:

    • Scheduling (e.g., timetabling exams without conflicts).
    • Register allocation in compilers.
    • Frequency assignment in wireless networks.
    • Map colouring.

Graph colouring

  • Origins:

    • Four Colour Problem (1852, Francis Guthrie), asking whether four colours suffice to colour any map so that no adjacent regions share a colour.
    • Four Colour Theorem proved in 1976 by Appel and Haken using computer assistance.

0–1 Knapsack

  • Optimisation problem: Select a subset of items, each with a value and weight, to maximise total value without exceeding the weight capacity.

  • Each item can be taken (1) or left (0).

  • Decision problem: Given a set of items with values and weights, a maximum capacity \(W\), and a target value \(V\), is there a subset whose total weight ≤ \(W\) and total value ≥ \(V\)?

0–1 Knapsack

  • Complexity:

    • Decision version is NP-complete.
    • Optimisation version is NP-hard.
    • Solvable in \(O(nW)\) via dynamic programming (pseudo-polynomial time).

0–1 Knapsack

0–1 Knapsack

  • Applications:

    • Budget allocation.
    • Cargo loading.
    • Project selection with resource limits.
    • Investment portfolio optimisation.

0–1 Knapsack

  • Origins:

    • Studied in the 19th and early 20th centuries in the context of resource allocation problems.
    • Became a classic combinatorial optimisation problem in operations research by mid-20th century.
    • Named “knapsack” because of the analogy to packing items in a backpack.

Travelling Salesman Problem (TSP)

  • Optimisation problem: Find the shortest possible tour that visits each city exactly once and returns to the starting city.

  • Decision problem: Given a set of cities, distances between them, and a maximum length \(D\), is there a tour visiting each city exactly once with total length ≤ \(D\)?

  • Complexity:

    • Decision version is NP-complete.
    • Optimisation version is NP-hard.
    • Exact algorithms are exponential (e.g., Held–Karp DP in \(O(n^2 2^n)\)).

Travelling Salesman Problem (TSP)

  • Applications:

    • Route planning and logistics.
    • Manufacturing (e.g., circuit board drilling).
    • Genome sequencing.
    • Data clustering.

Travelling Salesman Problem (TSP)

  • Origins:

    • Dates back to 18th-century mathematical puzzles (e.g., Hamiltonian cycles in 1850s).
    • Named and popularised in the mid-20th century by operations research and the RAND Corporation.
    • Studied extensively as a benchmark for combinatorial optimisation and computational complexity.